
/**
 * leetcode: 47, https://leetcode.cn/problems/permutations-ii/
 * Date: 2022-12-2
 * Author: guoyh
*/

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> visited;
        vector<int> path;
        int length = nums.size();
        // visited 标记需设置大小，否则剪枝条件会出现越界访问 visited[0] 不存在
        visited.resize(length);
        sort(nums.begin(), nums.end());
        dfs(res, nums, length, 0, path, visited);

        return res;
    }

    // res: 记录算法的返回结果
    // nums: 算法输入的数组
    // length: 已排列的list 长度
    // index: 填到第几个数
    // path：已生成的排列，中间结果
    // visited：记录某个位置的数字是否被用过
    // 回溯算法框架
    void dfs(vector<vector<int>>& res, vector<int>& nums, int length, int index, vector<int>& path, vector<int>& visited){
        if(length == index){
            res.push_back(path);
            return;
        }
        //要点： 代表选择的控制变量怎么设置。固定设置为数组长度，实际上每一层选择是逐渐减少的，如，开始有3个选择 index = 1,2,3这几个位置
        // 下一层就只有2个选择 index = 2,3 等。这一点通过剪枝条件来实现
        for(int i = 0; i < length; i++){
            // 剪枝，很重要, true 表示选过 还是false 代表选过了？
            // 选择，visited = true，取消选择 visited = false。取消选择的条件是 nums[i] == nums[i-1] && !visited[i-1]
            // 单独看 visited = false, 既可以说取消选择，也可能是 未选择过，初始值
            // 重要：visited[i] 剪枝条件遗漏了，结果里出现了 [1,1,1],[1,2,2]
            if(visited[i] || (i > 0 && nums[i] == nums[i-1] && visited[i-1] == false)){
                continue;
            }

            visited[i] = true;
            path.push_back(nums[i]);

            dfs(res, nums, length, index + 1, path, visited);

            visited[i] = false;
            path.pop_back();
        }
    }

};

void test_01(){
    Solution slu;
    vector<int> input = {1,1,2};
    vector<vector<int>> res = slu.permuteUnique(input);
    assert(res.size() == 3);
}

int main(){

    test_01();

    return 0;
}